package com.ting.test.algorithms.查找算法.归并查找;

/**
 * 假设有数组 arr=new int[]{4,2,5,7,3,1,9,5,5,66,12,32};
 * 找出每个元素前面比该元素小的数的总和
 * 解题思路
 * 利用归并查找的特性
 * 归并查找的特点是在合并阶段，左右两边的两个待合并的子数组一定是有序的
 */
public class 小和问题 {
    public static void main(String[] args) {
        int[] arr = new int[]{4, 2, 5, 7, 3, 1, 9, 5, 5, 66, 12, 32};

        if (arr == null || arr.length == 1) {
            return;
        }

        int result = func(arr, 0, arr.length - 1);
        System.out.println(result);
    }

    private static int func(int[] arr, int L, int R) {
        if (L == R) {//base case
            return 0;
        }

        int M = L + ((R - L) >> 1);
        return func(arr, L, M) + func(arr, M + 1, R) + merge(arr, L, M, R);
    }

    private static int merge(int[] arr, int l, int m, int r) {
        int[] help = new int[r - l + 1];
        int index = 0;
        int count = 0;
        int lindex = l;
        int rindex = m + 1;
        while (lindex <= m && rindex <= r) {
            //注意左右两个子数组都是有序的因此 如果arr[l] < arr[r] 则表示arr[i]小于r之后的所有元素
            count += arr[lindex] < arr[rindex] ? arr[lindex] * (r - rindex + 1) : 0;
            //合并时，如果
            help[index++] = arr[lindex] < arr[rindex] ? arr[lindex++] : arr[rindex++];
        }
        //到此说明是左边越界
        while (rindex <= r) {
            help[index++] = arr[rindex++];
        }
        //到此说明是右边越界
        while (lindex <= m) {
            help[index++] = arr[lindex++];
        }

        for (int i = 0; i < help.length; i++) {
            arr[l+i] = help[i];
        }

        return count;
    }
}
